\input basic
\output {\page}
\magnify {1100}
\parskip 12 pt
\ctrline {\bf CS154 ASSIGNMENT 4}
\vskip 36 pt
\parindent 0 pt
\ctrline {Assigned Friday, April 22, due Friday, April 29}
\vskip 12 pt
Do problems 3.21, 3.25, 3.26, and 3.28, in addition to the following:

I.

(a) Let $S$ be the set of all Pascal programs.  Let $L$ be the set of
all strings of the form $0↑{n}1↑{n}$.  Find a gsm that maps $S$ onto
$L$.  (Be sure that for every input string in $S$ either the gsm rejects
it or the output of the gsm is a string in $L$, and that every string
in $L$ is the output of the gsm for some input string in $S$).

(b) What does this imply about the set of all Pascal programs?

II. Find decision procedures that work directly on a regular expression
(no fair converting to a finite automaton) to do the following:

(a) determine whether the regular expression corresponds to the empty
set.  Examples:
$$(\{\}a + \{\})b {\hbox {\rm \ is empty.}}$$
$${\{\}}↑{*} {\hbox {\rm \ is not empty.}}$$
(Hint:  find a recursive algorithm.)

(b) determine whether the regular expression corresponds to an infinite
set.  (Hint:  Define four kinds of regular expression, namely $\{\}$,
$\epsilon$, all regular expressions corresponding to infinite sets,
all other regular sets.  Come up with an inductive algorithm.)

III. Extra credit (we expect no one to solve this problem)

You might notice that every set that we have proven non-regular
so far could have been proven non-regular by the ``generalized pumping
lemma'' stated in problem 3.2, so that we never really needed to
use our nifty closure properties.  Is this always the case?
More formally, let us call a language ``pumpable'' if it satisfies
the generalized pumping lemma.  Is there a language that is pumpable
but not regular?  (Be careful not to overlook the possibility that
$i=0$ in the generalized pumping lemma.)

\vfill\eject\end